#include <iostream>
using namespace std;
#include <algorithm>
#include <vector>

class Solution 
{
public:
    int maxSumAfterPartitioning(vector<int>& nums, int k)
    {
        int sum = 0, sz = nums.size();
        sort(nums.begin(), nums.end());
        int n = sz / k, m = sz % k;
        sz--;
        for (int i = 0; i < n; i++)
        {
            sum += nums[sz--] * k;
        }

        sum += nums[sz] * m;

        return sum;
    }
};

int main()
{
    Solution s;
    //vector<int> nums = { 1,15,7,9,2,5,10 };
    vector<int> nums = { 1 };
    int ret = s.maxSumAfterPartitioning(nums, 3);
    return 0;
}